package com.hardydou.concurrent;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

/**
 * 斐波那契 数列 示例
 * 1、递归法
 * 2、动态规划
 * 3、并行法
 * 4、forkjoin 法
 *
 * @author hardy
 */
public class FibonacciDemo {


    public static BigInteger forkJoinCalFibonacci(int n, int poolSize) {

        ForkJoinPool pool = new ForkJoinPool(poolSize);
        BigInteger r = pool.invoke(new FibonacciFJ(n));
        return r;
    }

    /**
     * 递归法
     *
     * @param n
     * @return
     */
    public static BigInteger recursiveFibonacci(int n) {
        if (n < 2) {
            return BigInteger.ONE;
        }
        return recursiveFibonacci(n - 1).add(recursiveFibonacci(n - 2));
    }


    /**
     * 动态规划
     *
     * @param n
     * @return
     */
    public static BigInteger iterativeFibonacci(int n) {
        BigInteger n1 = BigInteger.ONE;
        BigInteger n2 = BigInteger.ONE;
        // n1 + n2
        BigInteger fi = BigInteger.valueOf(2);
        for (int i = 2; i <= n; i++) {
            fi = n1.add(n2);
            n1 = n2;
            n2 = fi;
        }

        return fi;
    }

    public static BigInteger parallelFibonacci(int itemNum, int threadNum) throws Exception {
        final Matrix matrix = new Matrix(1, 1, 1, 0);
        // (f0, 0; f1, 0)
        final Matrix primary = new Matrix(1, 0, 1, 0);
        // 每个线程要计算的 相乘的项数
        final int workload = itemNum / threadNum;
        // (num / threadNum) 可能存在除不尽的情况，所以最后一个任务计算所有剩下的项数
        final int lastWorkload = itemNum - workload * (threadNum - 1);

        List<Callable<Matrix>> tasks = new ArrayList<>(threadNum);
        for (int i = 0; i < threadNum; i++) {
            if (i < threadNum - 1) {
                // 为了简洁，使用 Lambda 表达式替代要实现 Callable<Matrix> 的匿名内部类
                tasks.add(() -> matrix.pow(workload));
            } else {
                tasks.add(() -> matrix.pow(lastWorkload));
            }
        }

        ExecutorService threadPool = Executors.newFixedThreadPool(threadNum);
        // 执行所有任务，invokeAll 会阻塞直到所有任务执行完毕
        List<Future<Matrix>> futures = threadPool.invokeAll(tasks);
        Matrix result = primary.copy();
        // (matrix ^ n) * (f0, 0; f1, 0)
        for (Future<Matrix> future : futures) {
            result = result.mul(future.get());
        }

        threadPool.shutdown();

        return result.c;
    }

}


/**
 * 并行计算法
 *
 * @author hardy
 */
class Matrix {

    /**
     * 左上角的值
     */
    public final BigInteger a;
    /**
     * 右上角的值
     */
    public final BigInteger b;
    /**
     * 左下角的值
     */
    public final BigInteger c;
    /**
     * 右下角的值
     */
    public final BigInteger d;

    public Matrix(int a, int b, int c, int d) {
        this(BigInteger.valueOf(a), BigInteger.valueOf(b),
                BigInteger.valueOf(c), BigInteger.valueOf(d));
    }

    public Matrix(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    /**
     * multiply
     *
     * @param m multiplier
     * @return
     */
    public Matrix mul(Matrix m) {
        return new Matrix(
                // a*a + b*c
                a.multiply(m.a).add(b.multiply(m.c)),
                // a*b + b*d
                a.multiply(m.b).add(b.multiply(m.d)),
                // c*a + d*c
                c.multiply(m.a).add(d.multiply(m.c)),
                // c*b + d*d
                c.multiply(m.b).add(d.multiply(m.d)));
    }

    /**
     * power of exponent
     *
     * @param exponent
     * @return
     */
    public Matrix pow(int exponent) {
        Matrix matrix = this.copy();

        for (int i = 1; i < exponent; i++) {
            matrix = matrix.mul(this);
        }

        return matrix;
    }

    public Matrix copy() {
        return new Matrix(a, b, c, d);
    }

}


class FibonacciFJ extends RecursiveTask<BigInteger> {

    private int n;

    public FibonacciFJ(int n) {
        this.n = n;
    }

    @Override
    protected BigInteger compute() {
        if (n < 2) {
            return BigInteger.ONE;
        }
        FibonacciFJ left = new FibonacciFJ(n - 1);
        FibonacciFJ right = new FibonacciFJ(n - 2);
        left.fork();
        right.fork();
        BigInteger r = left.join().add(right.join());
        return r;
    }
}
